COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00043 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a53.tex[154,phy] \today\hfill}

\bigskip

\line{\bf PROBLEMS FOR THE FORMAL LANGUAGE BOOK\hfill}

\medskip
\line{[Programming assignment; unused]\hfill}

Where $R↓i$ is a relation and $S↓i$ a set, write and test procedures for
$R↓1\circ R↓2$, $S↓1\circ R↓2$, $R↓1\circ S↓2$, $S↓1\circ S↓2$,
$R↓1\cup R↓2$, $R↓1\cap R↓2$, $\bar R$, $R↑{-1}$, $R↑i$, $R↑+$, $R↑{\ast}$;
to initialize relations and sets to $\emptyset$ and~$\bar \emptyset$;
to initialize relations to~$I$; and to iterate $R:=R\cup f(R)$ to convergence.

Later: Test whether a relation is a function, a partial function, one-to-one,
onto, transitive, an equivalence relation. From an equivalence relation $≡$
construct a canonical function~$f$, such that $x\circ f=y\circ f$ iff $x≡y$.
Convert a transition relation to minimized form, $\delta'↓a=f↑{-1}\circ
\delta↓a\circ f$.

\bigskip
\line{[FM's; unused?]\hfill}

Show that an NFM to accept a language with shortest string of length~$n$
must have at least $n+1$ states. Exhibit a language for which the required
number of states is~10, whether we use an NFM or a~DFM.

\bigskip
\line{[NFMs; unused; homework only]\hfill}

\disleft 20pt:(1):
Write a program that takes a NFM, with state set $Q=\{1,2,\ldots,n\}$,
and converts it to a DFM with state set $\{1,2,\ldots,2↑n\}$.

\disleft 20pt:(2):
Write a  program that eliminates unreachable states from a DFM, and combines
useless states into a single dead state.

\bigskip
\line{[NFMs; homework, April 86]\hfill}

An operation to search a text file for an occurrence of a particular string,
(for example, a {\tt FIND} or {\tt SUBSTITUTE} operation in a text editor)
can be expressed as an NFM. If the task is to find string {\tt BAABABBAB}, 
the NFM~is:

$$\vcenter{\halign{$\hfil#\hfil$\xskip
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\cr
&A,B\cr
\noalign{\bigskip}
&&B&&A&&A&&B&&A&&B&&B&&A&&B\cr
\Rightarrow&0&&1&&2&&3&&4&&5&&6&&7&&8&&9\cr
}}$$

\bigskip\noindent
By converting the NFM to a DFM, one gets a fast search algorithm:

\smallskip
{\obeylines\obeyspaces\let =\ \tt
        STATE:=Q0
        WHILE NOT EOF DO
           BEGIN
              READ(C)
              STATE:=DELTA [STATE,C];
              IF ACCEPTING [STATE] THEN PROCESS
           END;
}

\disleft 20pt:(A):
Perform the conversion to DFM for the NFM above.

\disleft 20pt:(B):
Show that for any search string the number of states in the DFM is always
the same as in the NFM.

\disleft 20pt:(C):
How could you search at the same time for every occurrence of string
{\tt BABAA}? (I.e., search for strings {\tt BAABABBAB} or {\tt BABAA} at the
same time.)

\bigskip
\line{[FA's; unused]\hfill}

Give a DFM for
$${\rm shuffle}(\{a↑{\ast}b↑{\ast}c↑{\ast}\},\{a↑{\ast}b↑{\ast}c↑{\ast}\})\,.$$

Solution: Here is a NFM

$$\vcenter{\halign{$\hfil#\hfil$\qquad%
&$\hfil#\hfil$\xskip%
&$\hfil#\hfil$\quad%
&$\hfil#\hfil$\quad%
&$\hfil#\hfil$%
&$\hfil#\hfil$\xskip%
&$\hfil#\hfil$\quad%
&$\hfil#\hfil$\qquad%
&$\hfil#\hfil$\xskip%
&$\hfil#\hfil$\quad%
&$\hfil#\hfil$\qquad%
&$\hfil#\hfil$\xskip%
&$\hfil#\hfil$\cr
&&a&&a&&b&&a&c&&b&c\cr
\noalign{\bigskip}
&&&\epsilon&&&&\epsilon&&&\epsilon\cr
\Rightarrow&aa&&&&ab&&&ac&&&bc\cr
\noalign{\bigskip}
&&&&\epsilon\cr
&&&&&&b\cr
\noalign{\bigskip}
&&&&&bb\cr}}$$

\noindent
which can be simplified to

$$\vcenter{\halign{$\hfil#\hfil$\qquad
&$\hfil#$\xskip%
&$\hfil#\hfil$\quad%
&$\hfil#\hfil$\qquad%
&$\hfil#$\xskip%
&$\hfil#\hfil$\quad%
&$\hfil#\hfil$\qquad%
&$\hfil#$\xskip%
&$\hfil#$\cr
&a&b&&a&c&&b&c\cr
\noalign{\bigskip}
&&&\epsilon&&&\epsilon\cr
\Rightarrow&ab&&&ac&&&bc\cr}}$$

\noindent
and determinized and minimized to

$$\vcenter{\halign{$\hfil#\hfil$\qquad
&$\hfil#$\xskip%
&$\hfil#\hfil$\quad%
&$\hfil#\hfil$\qquad%
&$\hfil#$\xskip%
&$\hfil#\hfil$\quad%
&$\hfil#\hfil$\qquad%
&$\hfil#$\xskip%
&$\hfil#\hfil$\quad%
&$\hfil#\hfil$\qquad%
&$\hfil#$\cr
&a&b&&a&c&&b&c&&{\rm any}\cr
\noalign{\bigskip}
&&&c&&&b&&&a\cr
\Rightarrow&1&&&2&&&3&&&4\cr}}$$

\noindent
In short, if the string contains a $b$ that is preceded by a~$c$ and
followed by an~$a$, it is rejected.

\bigskip
\line{[DFMs; used Fall `84]\hfill}

Show the following are equivalent for deterministic finite
automata:

\disleft 20pt:(1): $(\forall x\in\Sigma↑{\ast})(\exists y\in\Sigma↑{\ast})
(\forall q\in Q)(q\,\delta↓{xy}\,q)$. That is, every string can be extended
on the right to make a string whose transition function is the identity
function.

\disleft 20pt:(2): For every letter $a\in\Sigma$, column~$a$ of the
transition function table contains every state.

\disleft 20pt:(3): For every letter $a\in\Sigma$, column~$a$ does not
contain any state twice.

\bigskip
\line{[Programming; NFMs; unused]\hfill}

\disleft 20pt:(A):
Write a program to convert a NFM to a DFM.

\disleft 20pt:(B):
Write a program to eliminate unreachable states from a DFM.

\disleft 20pt:(C):
Write a program to minimize a DFM in which all states are reachable.

\bigskip
\line{[Pumping]\hfill}

Prove, by application of a generalized sequential machine (alias: sequential
transducer) mapping that Pascal is not a regular language. (Remember that
almost anything can appear in a string constant.) If you don't know Pascal
at all, substitute another language with nested block structures.

\bigskip
\line{[Pumping]\hfill}

Definition [RWF: see Autumn `84 midterm]

If $x$ and $y$ are strings, ${\rm shuffle}(x,y)$ 
is the set of all strings obtainable
by shuffling the characters of $x$ and~$y$ like two decks of cards,
not necessarily in perfect alternation. Formally, shuffle 
$(x,y)=\{x↓1y↓1x↓2y↓2\ldots x↓ny↓n\}$, where the $x↓i$ and $y↓i$ are
(possibly empty) strings, and $x↓1x↓2\ldots x↓n=x$, $y↓1y↓2\ldots y↓n=y$.
If $L↓1$, $L↓2$ are languages, ${\rm shuffle}(L↓1,L↓2)=\bigcup\{\,{\rm shuffle}
(x,y)\mid x\in L↓1,y\in L↓2\,\}$.

\disleft 20pt:(A):
If $L↓1$ and $L↓2$ are FMLs, is ${\rm shuffle}(L↓1,L↓2)$ a FML?
(Proof or counterexample.)

Definition. If $L$ is a language, ${\rm shuffle}↑{\ast}(L)$ is the result
of shuffling arbitrarily many strings of~$L$. That is, 
${\rm shuffle}↑0(L)=\{\epsilon\}$,
${\rm shuffle}↑{i+1}(L)={\rm shuffle}\bigl(L,{\rm shuffle}↑i(L)\bigr)$,
${\rm shuffle}↑{\ast}(L)=\bigcup↓{i≥0}{\rm shuffle}↑i(L)$.

\disleft 20pt:(B):
If $L$ is a FML, is ${\rm shuffle}↑{\ast}(L)$ a FML? (Proof or counterexample.)

\bigskip
\line{[Pumping]\hfill}

\disleft 20pt:(A):
Is ${\rm shuffle}(\{b↑{\ast}\},\{a↑ib↑ic↑i\})$ a CFL?

\disleft 20pt:(B):
Is ${\rm shuffle}(\{a↑{\ast}b↑{\ast}c↑{\ast}\},\{a↑ib↑ic↑i\})$ a CFL?

Prove your answers.

Solutions.

\disleft 20pt:(A):
Intersect with $\{a↑{\ast}b↑{\ast}c↑{\ast}\}$ to get 
$\{\,a↑ib↑jc↑i\mid j≥i\,\}$. Then take $a↑nb↑nc↑n$, where $n$ is the
pumping constant, and pump~$c$'s; that is, give the $c$'s weight one.

\disleft 20pt:(B):
?

\bigskip
\line{[Pumping]\hfill}

The {\it scrambles\/} of a string are the set of rearrangements of its
characters; for example, the scrambles of $abbc$ are
$\{abbc,abcb,acbb,babc,bacb,bbac,bbca,bcab,bcba,cabb,cbab,cbba\}$.
The {\it scramble\/} of a language is the set of scrambles of its strings.

\disleft 20pt:(A):
Must the scramble of a FML be a FML?

The {\it fold\/} of a language $L$ contains, for every string
$x↓1x↓2\ldots x↓ny↓ny↓{n-1}\ldots y↓1\in L$ ($x↓iy↓i\in\Sigma↑{\ast}$),
the string $x↓1\hat{y}↓1x↓2\hat{y}↓2\ldots x↓n\hat{y}↓n$.

\disleft 20pt:(B):
Must the fold of a FML be a FML?

Solution.

\disleft 20pt:(A):
No; scrambling $\{(AB)↑{\ast}\}$ and intersecting with $A↑{\ast}B↑{\ast}$
gives a non-FML.

\disleft 20pt:(B):
Yes; nondeterministically pick characters as coming from $x$ or~$y$, and
compute $\delta↓x$ and~$\delta↓y$ as you go. At the end, an accepting state
is one for which $S\circ\delta↓x\circ\delta↓y\circ F$. [Use $Q↑-$ for~$S$,
$Q↑+$ for~$F$.]

\bigskip
\line{[GSMs; unused]\hfill}

Prove or disprove: The image of a FML under a GSM transduction is a FML.

Solution: Let finite generator
$M↓1$ generate $L↓1$, an arbitrary FML. Compose $M↓1$ with
arbitrary GSM,~$M↓2$. Then $M↓1\circ M↓2$ is a GSM and a generator, i.e.,
a~FMG, so what it generates is a FML. But what it generates is the image of
an arbitrary FML under an arbitrary GSM transduction.

\bigskip
\line{[DGSMs]\hfill}

If $L$ is a FML, show it is a DFT image of $\{(0\cup 1)↑{\ast}\}$.

\bigskip
\line{[DGSMs; H and U, page 246; unused]\hfill}

True or false: determinism of GSMs is preserved under

\disleft 20pt:(A): 
Composition, $M↓1\circ M↓2$.

\disleft 20pt:(B): 
Dual, $\hat{M}$.

\disleft 20pt:(C): 
Converse, $M↑{-1}$.

\disleft 20pt:(D): 
Concatenation, $M↓1\otimes M↓2$. [Define determinism of acceptance carefully.]

\bigskip
\line{[DGSMs]\hfill}

Is there a DGSM with IO relation $R$ such that $\{A↑{\ast}B↑{\ast}C\}\circ R
=\{(D\cup DE)↑{\ast}\}$?

Answer: While reading $A$'s, $M$ must cycle, etc., so output must be
``mostly'' periodic. But there are arbitrarily long strings in
$(D\bigcup DE)↑{\ast}$ that don't have this almost periodic property.

\bigskip
\line{[GSMs; used May 86]\hfill}

\disleft 20pt:(A):
Prove that, if $M$ is a GSM with input-output relation $R↓M$, there is a
number~$n$ for which every pair of strings $x$, $y$ for which $|x|≥n$,
$|y|≥n$, $xR↓My$, can be broken up as $x=x↓1x↓2x↓3$, $y=y↓1y↓2y↓3$,
with $|x↓2|≥1$, $|y↓2|≥1$, and $x↓1x↓2↑ix↓3R↓My↓1y↓2↑iy↓3$ for all $i≥0$.

\disleft 20pt:(B):
Can it also be required that $|x↓1x↓2|≤n$ and $|y↓1y↓2|≤n$?

\bigskip
\line{[PDMs; unused]\hfill}

Let $z$ be a sequence of pushes and pops. Show that exactly one of the following
holds:

\display 20pt:$\bullet$:
$z$ can not be applied to any stack.

\display 20pt:$\bullet$:
There is a unique shortest stack $u$ to which $z$ can be applied, resulting
in~$v$, and the before/after relation of~$z$ is 
$\{\,\langle xu,xv\rangle\mid x\in\Gamma↑{\ast}\,\}$.

\bigskip
\line{[Regular expressions]\hfill}

 In the graph with nodes $\{1,2,3,4\}$, the edges,
labeled, are:

$$\vcenter{\halign{$\ctr{#}$\quad&$\ctr{#}$\quad&$\ctr{#}$\cr
1&a&2\cr
2&b&3\cr
3&c&4\cr
4&d&1\cr
1&e&4\cr
4&f&3\cr
3&g&2\cr
2&h&1\cr}}$$
Give a regular expression for the labels of all paths from 1 to~3.

$$\vcenter{\halign{$\ctr{#}$\quad&$\ctr{#}$\quad&$\ctr{#}$\quad%
&$\ctr{#}$\quad&$\ctr{#}$\quad&$\ctr{#}$\quad&$\ctr{#}$\cr
&&&a\cr
\noalign{\smallskip}
&1&&&&2\cr
\noalign{\smallskip}
&&&h\cr
\noalign{\medskip}
d&&e&&g&&b\cr
\noalign{\medskip}
&&&f\cr
\noalign{\smallskip}
&4&&&&3\cr
\noalign{\smallskip}
&&&c\cr}}$$

\bigskip
\line{[Regular expressions]\hfill}

 In the regular expression for the number of paths
from a node to itself in the complete graph on $n$~nodes, how many stars
are needed? (An upper bound suffices.)

\bigskip
\noindent{\bf Answer.}

$$\vcenter{\halign{$\ctr{#}$\qquad&$\ctr{#}$\qquad&$\ctr{#}$&$\ctr{#}$%
&$\ctr{#}$\quad&$\ctr{#}$\cr
&&&&&2\cr
\noalign{\bigskip}
&\epsilon\cr
0&&&1&&3\cr
\noalign{\smallskip}
&&&&&=n\cr
\noalign{\smallskip}
&&\epsilon\cr
\noalign{\bigskip}
&&&4&=n+1\cr}}$$

\bigskip\noindent
Labels initially have 0~stars. Eliminating a node other than~1 replaces
labels with $k$~stars by labels with $4k+1$ stars. Let $f(i)$ be the number
of stars when $i$~nodes (other than node~1) have been eliminated; 
$$\eqalign{f(0)&=0\,;\cr
f(i+1)&=4f(i)+1\,.\cr}$$
Adding a constant to both sides, 
$f(i+1)+c=4f(i)+1+c$;
letting $1+c=4c$, or $c=1/3$, we get:
$$\eqalign{f(i+1)+{1\over 3}&=4\biggl(f(i)+{1\over 3}\,\biggr)\,;\cr
\noalign{\smallskip}
f(i)+{1\over 3}&=4↑i\biggl(f(0)+{1\over 3}\,\biggr)\,;\cr
\noalign{\smallskip}
f(i)&={4↑i-1\over 3}\cr}$$
and after eliminating node 1, we have one more star, for $4↑i+2\over 3$
as total.

\bigskip
\line{[DFMs; used as homework, April 86]\hfill}

\disleft 20pt:(A):
 Define an NFA for the set of strings over $\Sigma=\{a,b\}$ which 
consist of:

\disleft 30pt:: a string of $a$'s and $b$'s with the number of $b$'s
divisible by~3; then, two consecutive~$a$'s; then a string of $a$'s
and~$b$'s with an even number of~$b$'s.

\disleft 20pt:(B):
 Construct an equivalent DFA.

\disleft 20pt:(C):
 Minimize it.

\bigskip
\line{[Regular expressions]\hfill}

\disleft 20pt:(A):
Find a constant $C$ such that every regular expression of length~$k$ is
accepted by a nondeterministic finite automaton of at most $Ck$ states.

\disleft 20pt:(B):
Show that there is no constant $C$ such that every regular expression of
length~$k$ is accepted by a deterministic finite automaton of at most
$Ck$~states.

Hint: consider $(A+B)↑{\ast}A(A+B)↑{100}$.

\bigskip
\line{[PDMs; unused]\hfill}

Final: Define NPDMs in such a way that there is a {\sl very simple\/} way
to do time reversal, and/or input-output reversal, analogous to
$\hat{M}$ and $M↑{-1}$ for gsms. You will be graded on simplicity as well
as correctness.

\bigskip
\line{[DCFLs, DGSMs, H and U, page 246]\hfill}

True or false:

\disleft 20pt:(A):
The image of a DPDL under a DGSM mapping is a DPDL.

\disleft 20pt:(B):
The image of a non-DPDL under a DGSM mapping is a non-DPDL.

\bigskip
\line{[DPDMs]\hfill}

Is $\{\,w\hat{w}\mid w\in(0\cup 1)↑{\ast}\,\}$ a DCFL? (Hard.)

Is $\{\,0↑i1↑i\mid i≥1\,\}\cup\{0↑i1↑{2i}\mid i≥1\,\}$ a DCFL?
(Very hard.)

\bigskip
\line{[DPDMs]\hfill}

Suppose $L$ is recognizable by a DPDM. Can it necessarily be recognized
by a DPDM that reads a character at every step? (Proof or counterexample.)

\bigskip
\line{[PDMs; unused]\hfill}

Suppose we define PDMs as flowcharts, in much the same way as was done
in the course, but take as the only input operation a {\tt READ} that branches
according to the input character, halting immediately on an end-of-file
condition, either accepting or rejecting.

\disleft 20pt:(A):
Does this restriction narrow the set of languages accepted by NPDMs?

\disleft 20pt:(B):
Does this restriction narrow the set of languages accepted by DPDMs?

\bigskip
\line{[Counter machines; H\&U Ex.~6.2b, f]\hfill}

\disleft 20pt:(A):
Let $L=\{(a↑ib)↑i\}=\{ab,aabaab,aaabaaabaaab,\ldots\}$.
Show that $\bar{L}$ is a NCL.

Solution: Strings are in $\bar{L}$ if they begin with~$b$ or end with~$a$,
or if any group of~$a$'s is not equal to the total number of~$b$'s.

\figbox 3.5truein:

\disleft 20pt:(B):
Let $L=\{(a↑ib↑i)↑i\}=\{ab,aabbaabb,\ldots\}$. Show that $\bar{L}$ is a NCL.

Solution: Like (A) but messier.

\bigskip
\line{[DPDMs and counter machines; unused; very hard]\hfill}

Find a DCFL not accepted by any deterministic one-counter machine. 

Variants of the above:

Show that there is a CFL not accepted by any NCM.

Show that the two parenthesis language $L(\,)[\,]$ is not accepted by a NCM.

\bigskip
\line{[GSMs and counter machines]\hfill}

Let $M$ be a two-counter transducer. Show that there are two one-counter
transducers, $M↓1$ and~$M↓2$, for which $R↓M=R↓{M↓1}\circ R↓{M↓2}$.

Solution: Let $M↓0$ be a GSM that guesses a computation of~$M$, reads the
input characters of that computation, and writes the computation itself.
Let $M↓1$ be a filter that checks whether the first counter is described
as behaving right in the computation it reads, and $M↓2$ is the same for
the second counter. $M↓3$~reads a computation of~$M$, and writes only the
output of the computation. Then $M↓0\circ M↓1\circ M↓2\circ M↓3$ has IO
relation~$R↓M$. Notice that $M↓0\circ M↓1$ is a one-counter transducer,
as is $M↓2\circ M↓3$.

\bigskip
\line{[CFGs; used May 86]\hfill}

Given the grammar
$$\eqalign{S=E&→T\mid E+T\cr
T&→F\mid T*F\cr
F&→(E)|a|b|c\cr}$$
Show derivation trees for the strings
$$a\,,\qquad a+b\,,\qquad a*b\,,\qquad a+(b+c)\,,\qquad a*b*c+b+a*c\,.$$


\bigskip
\line{[CFGs; unused]\hfill}

If $G$ is a context-free grammar in Chomsky normal form, and the shortest
string in $L(G)$ is of length~$n$, then the grammar uses at least
$\log↓2(n)$ variables.

\bigskip
\line{[CFLs]\hfill}

Let $G$ be the context-free grammar
$$\eqalign{S&→A\mid S+A\cr
A&→B\mid A*B\cr
B&→N\mid (S)\cr
N&→1\mid N1\cr}$$
Which character pairs can appear as substrings of sentential forms of~$G$?
As prefixes of sentential forms?

\bigskip
\line{[CFGs; unused]\hfill}

True-False: For every $n$, there is a CFL for which no grammar has fewer
than $n$ variables.

Solution? Is it true?


\bigskip
\line{[Pumping -- can this be a machine based pumping theorem?, DCFLs; unused]\hfill}

Let $L↓{ab}$ be those strings in $\{a,b,c,d\}↑{\ast}$ with as many $a$'s
as~$b$'s, and similarly $L↓{ac}$, $L↓{ad}$, $L↓{bc}$, $L↓{bd}$, $L↓{cd}$;
the complementary languages are $\bar{L}↓{ab}$, etc. Let $L$ be $a↑{\ast}b↑{\ast}
c↑{\ast}d↑{\ast}$. If you form intersections of two or more of these languages,
which are CFLs? If you form unions of two or more, which are DCFLs?

Answer: $L↓{ab}\cap L↓{ac}$ is not a CFL; if it were, the intersection
with $L$ would be, but Ogden's Theorem gets it.
$L↓{ab}\cap L↓{cd}\cap L$ is a CFL, by concatenation, but not
$L↓{ac}\cap L↓{bd}\cap L$. $L↓{ab}\cap L↓{cd}$ is not. 
If $L↓{ac}\cup L↓{ad}$ were a DCF, $\overline{L↓{ac}}\cap 
\overline{L↓{ad}}$ would
be also and so would the intersection with $a↑{\ast}c↑{\ast}d↑{\ast}$,
which is $a↑ic↑jd↑k$, $i≠j∧i≠k$. Ogdenize the~$a$'s.

\bigskip
\line{[Pumping lemma; unused]\hfill}

Let $L↓{(\,)}$ and $L↓{[\,]}$ be the languages of nested parentheses and
brackets, defined by the grammars
$$\eqalign{A&→\epsilon\mid (A)A\cr
B&→\epsilon\mid [B]B\cr}$$
Prove or disprove that the shuffle of $L↓{(\,)}$ and $L↓{[\,]}$ is a CFL.

\bigskip
\line{[Pumping, CFL's]\hfill}

Let $L$ be the language $\{x=y\times z\}$ where $x$, $y$, and $z$ must
be non-empty strings of decimal digits for which the equation is true.
Is $L$ a FAL, CFL, or neither? Prove your answer.

Answer: Suppose it were a CFL. Intersecting with the regular set
$\{10↑{\ast}20↑{\ast}1=10↑{\ast}1\times 10↑{\ast}1\}$ gives
$\{10↑i20↑i1=10↑i1\times 10↑i1\}$, also a CFL. Apply the pumping theorem,
with $i$ equal to the pumping constant. Notice that only zeroes may be pumped.
Absurd.

\bigskip
\line{[Ambiguity]\hfill}

Prove that $\{\,a↑ib↑jc↑kd↑l\mid i=k\hbox{ or }j=l\,\}$ is inherently ambiguous.

Is $\{\,a↑ib↑jc↑kd↑m\mid i=j\hbox{ or } k=m\,\}$ inherently ambiguous?

\bigskip
\line{[Inherent ambiguity; unused]\hfill}

If $L↓1$ is an unambiguous CFL, and $L↓2$ a FML, must there be an unambiguous
grammar for ${\rm shuffle}(L↓1,L↓2)$?

Answer: No. Let $L↓1=\{a↑ib↑ic↑jd\cup a↑ib↑jc↑j\}$, $L↓2=d↑{\ast}$. 
Intersecting ${\rm shuffle}(L↓1,L↓2)$ with $a↑{\ast}b↑{\ast}c↑{\ast}d$
gives the inherently ambiguous language $\{\,a↑ib↑jc↑kd\mid i=j\vee j=k\,\}$.
If $L↓1$ and $L↓2$ are on disjoint alphabets, the matter is different.

\bigskip
\line{[Inherent ambiguity; 5 students, Fall 84]\hfill}

In the course notes, it is shown that $a↑ib↑ic↑j\cup a↑ib↑jc↑j$ is
inherently ambiguous. What about $a↑ib↑ia↑j\cup a↑ib↑ja↑j$?

Solution: Take a grammar for $L↓2$. A slight modification results in a
grammar where variables are marked as following the last~$b$ or not.
Another slight change results in $c$'s rather than~$a$'s after the
last~$b$. Neither change introduces ambiguity, but the resulting
grammar for~$L↓1$ must be ambiguous, so that for~$L↓2$ must have been.

\bigskip
\line{[Inherent Ambiguity, GSMs]\hfill}

Let $L↓1$ be a CFL with unambiguous grammar $G$, and $L↓2$ a FML.

\disleft 20pt:(A):
Must there be an unambiguous grammar for $L↓1\cap L↓2$? (Proof or
counterexample.)

\disleft 20pt:(B):
Must there be an unambiguous grammar for $L↓1\cup L↓2$?

Solution.

\disleft 20pt:(A):
Compose the derivations of $L↓1$ with computations of a deterministic
filter for $L↓2$, and show uniqueness. See proof UCFLs closed under
converse DGSM transduction.

\disleft 20pt:(B):
?

\bigskip
\line{[CFLs, GSMs, ambiguity]\hfill}

Is the clas of unambiguous CFL's closed under:

\disleft 20pt:(A):
GSM transductions?

\disleft 20pt:(B):
converse GSM transductions?

\disleft 20pt:(C):
DGSM transductions?

\disleft 20pt:(D):
converse DGSM transductions?

Answer:

\disleft 20pt:(A):
No: $\{a↑ib↑ic↑jd\}\cup\{a↑ib↑jc↑je\}$ easily maps into $\{\,a↑ib↑jc↑k\mid
i=j\hbox{ or }j=k\,\}$.

\disleft 20pt:(B):
The GSM transductions are the same as the converse GSM transductions, so
the same example works.

\disleft 20pt:(C):
The solution of (A) works for (C) also.

\disleft 20pt:(D):
Take a string $x$. If accepted by~$M$, a DGSM, then $xR↓My$ for a unique~$y$.
If $y\in L$, an UCFL, there is a unique derivation tree. Then examine
the derivation tree for $x$ in the grammar for $L\circ M↑{-1}$. The value
of~$x$ at the leaves determines the value of~$y$ at the level above; the unique
derivation of~$y$ in~$L$, and computation of~$y$ from~$x$ by~$M$, determine
the rest uniquely.

\bigskip
\line{[DPDMs, ambiguity; solved in H and U; homework only]\hfill}

\disleft 20pt:(A):
If $L↓1$ is the language accepted by a DPDT, is there necessarily an 
unambiguous CFG for it?

\disleft 20pt:(B):
If $L↓2$ is the language generated by DPDT (the set of outputs of all possible
accepting computations), is there necessarily an unambiguous CFG for it?

Solution:

\disleft 20pt:(A):
Yes. [Construct CFG where derivations are uniquely determined by computations.]

\disleft 20pt:(B):
No. [Construct a DPDT that maps $da↑ib↑ic↑j$ to $a↑ib↑ic↑j$ and
$ea↑ib↑jc↑j$ to $a↑ib↑jc↑j$, rejecting all else.]

\bigskip
\line{GSMs; used May 86]\hfill}

A {\sl queue\/} is a memory device that, like a stack, holds a string;
it differs in that characters are pushed on one (say, the right) end and
popped off the other (left) end. Show that any program for a machine with
a tape, or two stacks, or two counters (your choice) can be translated
into a program for a machine with one queue as its only memory device.

\bigskip
\line{[TMs, unused]\hfill}

Show that a machine with a one-way-infinite storage tape, on which each
position may only be changed once, can simulate any Turing machine.

Solution: It suffices to show that it can simulate two counters. To simulate
one counter, we keep marks representing $+1$ in the odd numbered positions,
$-1$~in the even numbered positions. To add or subtract one, we locate the
first unmarked odd or even position and mark it. The counter is zero
when we find 1100, starting in an odd position. For two counters, we
intersperse.


\bigskip
\line{[Machine hierarchy; unused]\hfill}

A certain machine contains two variables, $x$ and $y$, initially zero.
It is able to test whether $x=y$, and to perform the operations
$x:=f(x)$ and $y:=f(y)$. The function~$f$ has the property that $f(x)>x$.
Compare the capabilities of this machine with finite machines, one-counter
machines, pushdown machines, and Turing machines.

Answer: It has the power of a one-counter machine.

\bigskip
\line{[TM's; June 86]\hfill}

True or false: It is decidable whether a D2CM halts on all inputs.

\bigskip
\line{TMs; unused]\hfill}

True or false: All NTM-computable functions are DTM-computable.

\bigskip
\line{[TMs]\hfill}

True or false: (June 86) If $R$ is the IO relation of a NTM, and $R$
is a partial function, must $R$ be the IO relation of a DTM?

\bigskip
\line{[REC, RE; unused]\hfill}

Let $L$ be a language that is neither RE nor co-RE. Let $L'=0\otimes L
\cup 1\otimes \bar{L}$. Which of the following are certain?

\disleft 20pt:(A):
$L'$ is RE.

\disleft 20pt:(B):
$L'$ is not RE.

\disleft 20pt:(C):
$L'$ is co-RE.

\disleft 20pt:(D):
$L'$ is not co-RE.

\noindent
Prove your answers.

\bigskip
\line{[RE]\hfill}

Which of these sets of machine descriptions are RE?

\disleft 20pt:(A):
Machines that accept at least two input strings.

Solution: RE. Search for triples $\langle x,y,z\rangle$ such that $x$ is a machine
of which $y$ and $z$ are computations with equal inputs. Print each~$x$.

\disleft 20pt:(B):
Machines that accept infinitely many input strings.

Solution: (Reduction.) Not RE.
Convert an autonomous machine that runs for $n$~steps
into a machine that accepts $\{\,a↑ib↑ic↑i\mid i≤n\,\}$.

\disleft 20pt:(C):
Machines that accept a language that is a CFL.

Solution: Same as (B).

\bigskip
\line{[REC, RE; unused]\hfill}

A function $f(x)$ is {\sl semicomputable\/} (co-semicomputable) if there
is a computable function $g(x,i)$ that is monotone in~$i$, and
$f(x)=\max↓i g(x,i)$ (respectively, $\min↓ig(x,i)$). That is, $f$~is
the limit of a series of functions that approaches it from below (above).
Show that a predicate is semicomputable (co semicomputable) iff it
characterizes an RE (co-RE) set, and computable iff it characterizes a
recursive set.

\bigskip
\line{[RE; unused; homework only]\hfill}

Define a particular language $L$ such that neither $L$ nor its complement
contecursively enumerable.




\bigskip
\parindent0pt
\copyright 1986 Robert W. Floyd.
First draft (not published)
June 20, 1986.
%revised date;
%subsequently revised.

\bye